package LeetCode.month04.day98;

/**
 * @author 16778
 * @date 2025/11/7 8:18
 * @description
 */
public class No2528 {

    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;
        long[] sum = new long[n+1];
        for (int i = 1; i <= n; i++) {
            sum[i]=sum[i-1]+stations[i-1];
        }
        long[] power = new long[n];
        Long min = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            power[i] = sum[Math.min(i+r+1,n)]-sum[Math.max(i-r,0)];
            min = Math.min(min,power[i]);
        }

        long left = min+k/n;
        long right = min+k+1;
        while(left+1<right){
            long mid = (left+right)/2;
            if(check(mid,power,r,k)){
                left = mid;
            }else{
                right = mid;
            }
        }
        return left;

    }

    private boolean check(long low, long[] power, int r, int k) {
        int n = power.length;
        long[] df = new long[n+1];
        long sumD = 0;
        int num = 0;
        for (int i = 0; i < n; i++) {
            sumD+=df[i];
            long m = low - (power[i]+sumD);
            if(m<=0){
                continue;
            }
            num+=m;
            if(num>k){
                return false;
            }
            sumD+=m;
            df[Math.min(n,i+r*2+1)]-=m;
        }
        return true;
    }


//    public long maxPower(int[] stations, int r, int k) {
//        int n = stations.length;
//        // 前缀和
//        long[] sum = new long[n + 1];
//        for (int i = 0; i < n; i++) {
//            sum[i + 1] = sum[i] + stations[i];
//        }
//
//        // 初始电量
//        long[] power = new long[n];
//        long mn = Long.MAX_VALUE;
//        for (int i = 0; i < n; i++) {
//            power[i] = sum[Math.min(i + r + 1, n)] - sum[Math.max(i - r, 0)];
//            mn = Math.min(mn, power[i]);
//        }
//
//        // 开区间二分
//        long left = mn + k / n;
//        long right = mn + k + 1;
//        while (left + 1 < right) {
//            long mid = left + (right - left) / 2;
//            if (check(mid, power, r, k)) {
//                left = mid;
//            } else {
//                right = mid;
//            }
//        }
//        return left;
//    }
//
//    private boolean check(long low, long[] power, int r, int k) {
//        int n = power.length;
//        long[] diff = new long[n + 1];
//        long sumD = 0;
//        long built = 0;
//        for (int i = 0; i < n; i++) {
//            sumD += diff[i]; // 累加差分值
//            long m = low - (power[i] + sumD);
//            if (m <= 0) {
//                continue;
//            }
//            // 需要在 i+r 额外建造 m 个供电站
//            built += m;
//            if (built > k) { // 不满足要求
//                return false;
//            }
//            // 把区间 [i, i+2r] 加一
//            sumD += m; // 由于 diff[i] 后面不会再访问，我们直接加到 sumD 中
//            diff[Math.min(i + r * 2 + 1, n)] -= m;
//        }
//        return true;
//    }
}
